package com.itheima.leetcode.od.b.logicalsimulation;

import java.util.ArrayList;
import java.util.stream.Collectors;

/**
 * (C卷,200分)- 根据IP查找城市（Java & JS & Python & C）
 * <p>
 * 题目描述
 * <p>
 * 某业务需要根据终端的IP地址获取该终端归属的城市，可以根据公开的IP地址池信息查询归属城市。
 * <p>
 * 地址池格式如下：
 * <p>
 * 城市名=起始IP,结束IP
 * <p>
 * 起始和结束地址按照英文逗号分隔，多个地址段采用英文分号分隔。比如：
 * <p>
 * City1=1.1.1.1,1.1.1.2;City1=1.1.1.11,1.1.1.16;City2=3.3.3.3,4.4.4.4;City3=2.2.2.2,6.6.6.6
 * <p>
 * 一个城市可以有多个IP段，比如City1有2个IP段。
 * <p>
 * 城市间也可能存在包含关系，如City3的IP段包含City2的IP段范围。
 * <p>
 * 现在要根据输入的IP列表，返回最佳匹配的城市列表。
 * <p>
 * 注：最佳匹配即包含待查询IP且长度最小的IP段，比如例子中3.4.4.4最佳匹配是City2=3.3.3.3,4.4.4.4，5.5.5.5的最佳匹配是City3=2.2.2.2,6.6.6.6
 * <p>
 * 输入描述
 * <p>
 * 输入共2行。
 * <p>
 * 第一行为城市的IP段列表，多个IP段采用英文分号 ';' 分隔，IP段列表最大不超过500000。城市名称只包含英文字母、数字和下划线。最多不超过100000个。IP段包含关系可能有多层，但不超过100层。
 * <p>
 * 第二行为查询的IP列表，多个IP采用英文逗号 ',' 分隔，最多不超过10000条。
 * <p>
 * 输出描述
 * <p>
 * 最佳匹配的城市名列表，采用英文逗号 ',' 分隔，城市列表长度应该跟查询的IP列表长度一致。
 * <p>
 * 备注
 * 无论是否查到匹配正常都要输出分隔符。举例：假如输入IP列表为IPa,IPb，两个IP均未有匹配城市，此时输出为","，即只有一个逗号分隔符，两个城市均为空；
 * 可以假定用例中的所有输入均合法，IP地址均为合法的ipv4地址，满足 (1~255).(0~255).(0~255)​​​​​​​.(0~255​​​​​​​) 的格式，且可以假定用例中不会出现组播和广播地址；
 * <p>
 * 用例
 * <p>
 * 输入	City1=1.1.1.1,1.1.1.2;City1=1.1.1.11,1.1.1.16;City2=3.3.3.3,4.4.4.4;City3=2.2.2.2,6.6.6.6
 * <p>
 * 1.1.1.15,3.3.3.5,2.2.2.3
 * <p>
 * 输出	City1,City2,City3
 * <p>
 * 说明
 * <p>
 * 1）City1有2个IP段，City3的IP段包含City2的IP段；
 * <p>
 * 2）1.1.1.15仅匹配City1=1.1.1.11,1.1.1.16，所以City1就是最佳匹配；2.2.2.3仅匹配City3=2.2.2.2,6.6.6.6，所以City3是最佳匹配；3.3.3.5同时匹配为City2=3.3.3.3,4.4.4.4和City3=2.2.2.2,6.6.6.6，但是City2=3.3.3.3,4.4.4.4的IP段范围更小，所以City3为最佳匹配；
 * <p>
 * 题目解析
 * <p>
 * 本题主要难点在于判断一个IP地址是否属于一个IP段范围。
 * <p>
 * 我的解决思路是，将IP地址转为整型数值，因为IP地址本质上是4*8位二进制数，所以每一个IP地址其实都能对应到一个整型数值。具体转化思路请见下面博客：
 * <p>
 * 整数与IP地址间的转换-CSDN博客
 * <p>
 * 而IP地址转为整型数值后，即可通过数值大小关系，判断某个IP地址是否属于某段IP范围。
 * <p>
 * 之后就是，遍历待查询的IP地址，去和每一个IP段范围匹配，如果可以匹配上，且对应IP段范围更小，则对应IP段的城市就是当前待查询IP的最佳匹配城市。
 */
public class FindCityByIP {
    public static void main(String[] args) {
        /*Scanner sc = new Scanner(System.in);

        ArrayList<Range> ranges = new ArrayList<>();

        // 城市IP列表
        String[] cities = sc.nextLine().split(";");
        // 带查询的IP列表
        String[] queryIps = sc.nextLine().split(",");*/

        // 城市IP列表
        String input1 = "City1=1.1.1.1,1.1.1.2;City1=1.1.1.11,1.1.1.16;City2=3.3.3.3,4.4.4.4;City3=2.2.2.2,6.6.6.6";
        String[] cities = input1.split(";");

        // 带查询的IP列表
        String input2 = "1.1.1.15,3.3.3.5,2.2.2.3";
        String[] queryIps = input2.split(",");

        System.out.println(getResult(cities, queryIps));
    }

    private static String getResult(String[] cities, String[] queryIps) {
        ArrayList<Range> ranges = new ArrayList<>();

        // 提取各个城市IP列表信息
        for (String city : cities) {
            String[] tmp = city.split("[=,]");
            ranges.add(new Range(tmp[0], tmp[1], tmp[2]));
        }

        ArrayList<String> list = new ArrayList<>();

        // 遍历待查询的IP地址
        for (String ip : queryIps) {
            long ipDec = ip2dec(ip);

            // 记录该目标IP地址的最佳匹配城市
            String city = "";
            // 记录最佳匹配城市IP段的长度
            long minLen = Long.MAX_VALUE;

            // 将带查询IP与城市IP段列表逐一匹配
            for (Range range : ranges) {
                // 如果带查询的IP地址 在某城市的IP段范围内，且该城市的IP段长度更小，则该城市为待查询IP的最佳匹配城市
                if (ipDec >= range.startIpDec && ipDec <= range.endIpDec && minLen > range.ipLen) {
                    city = range.city;
                    minLen = range.ipLen;
                }
            }

            list.add(city);
        }

        return list.stream().collect(Collectors.joining(","));
    }

    /**
     * IP地址转整型
     *
     * @param ip
     * @return
     */
    public static long ip2dec(String ip) {
        long res = 0;

        String[] blocks = ip.split("\\.");

        for (String block : blocks) {
            res = (Integer.parseInt(block)) | (res << 8);
        }

        return res;
    }

    static class Range {
        String city;
        long startIpDec;
        long endIpDec;

        long ipLen;

        public Range(String city, String startIpStr, String endIpStr) {
            this.city = city;
            // 将IP地址转为整型
            this.startIpDec = ip2dec(startIpStr);
            this.endIpDec = ip2dec(endIpStr);
            this.ipLen = this.endIpDec - this.startIpDec + 1;
        }

    }
}